Expression normalization

式の正規化

従来のLINQには、IQueryable<T>とIQueryProviderのインターフェイスを通じて、クエリプロバイダの概念があります。クエリプロバイダの役割は、クエリ式の定式化によって生成された式ツリーを受け取り、プロバイダに依存する実行可能なフォーマットに変換することです。最良の例は、以下に示すように、LINQ to SQLでしょう。

Traditional LINQ has the notion of query providers through the IQueryable<T> and IQueryProvider interfaces. The role of query providers is to take the expression trees generated by the formulation of query expressions and transform them into an executable format which is dependent on the provider. The best example is likely LINQ to SQL, as shown below:

code:C#

var ctx = new DataContext();

var res = from p in ctx.GetTable<Product>("Products")

where p.UnitPrice > 49.95m

select p.ProductName;

foreach (var p in res)

{

// ...

}

ここでは、クエリ式の作成により、単に IQueryable<string> 型のオブジェクトが作成され、変数 res に代入されます。このオブジェクトの Expression プロパティには、クエリの意図を表す式木が含まれており、大まかには以下のようになります。

In here, the formulation of the query expression merely builds an object of type IQueryable<string> which gets assigned to the res variable. This object contains an expression tree in its Expression property, representing the query intent, which will roughly look like:

code:query

Call(

methodinfoof(Queryable.Select<Product, string>),

Call(

methodinfoof(Queryable.Where<Product, Product>),

Parameter(

typeof(IQueryable<Product>),

"Products"

),

Lambda(

Member(p, propertyinfoof(Product.ProductName)),

p

)

),

Lambda(

GreaterThan(

Member(p, propertyinfoof(Product.UnitPrice)),

Constant(49.95)

),

p

)

)

foreachループによる反復をトリガーすると、クエリに関連付けられたクエリプロバイダは、式ツリーを実行可能な形式に変換し、反復して得られたオブジェクトの形で実体化された結果を得ることができます。LINQ to SQLの場合、式ツリーは以下のような意味的に等価なT-SQLクエリに変換されます。

Upon triggering the iteration through the foreach loop, the query provider associated with the query will transform the expression tree into an executable form in order to obtain materialized results in the form of objects yielded to the iteraton. In the case of LINQ to SQL, the expression tree gets translated into a semantically equivalent T-SQL query, like this:

code:SQL

SELECT p.ProductName FROM Products AS p WHERE p.UnitPrice > 49.95

これを実現するために、クエリプロバイダのコードはローカルで実行され、Queryable 型に定義された Where や Select などの標準的なクエリ演算子を表す MethodInfo オブジェクトをビルトインで認識しています。これは、クエリ式のローカルな翻訳には適していますが、異なるシステム間で式ツリーをシリアライズしようとすると、クライアント側のAPIとの結合が発生するため、破綻してしまいます。

In order to achieve this, the query provider’s code runs locally and has built-in awareness of MethodInfo objects that represent standard query operators like Where and Select defined on the Queryable type. That’s fine for a local translation of a query expression but breaks down when trying to serialize the expression tree between different systems, because it introduces a coupling with client-side APIs.

IRPは、前述のように、すべてのクエリ演算子を、識別子を使って表されるパラメータ化された観測可能な定義として表現することで、この問題を解決しています。これにより、IRPシステムのクライアント・ライブラリは、適切な言語投影（C#やVBのLINQ、Java、JavaScript、Pythonなどのfluent interface patternなど）から正規の形式に式を正規化することができます。例として、次のようなストリーミングに相当するクエリを考えてみましょう。

IRP solves this issue by representing all query operators as parameterized observable definitions represented using an identifier, as discussed earlier. This allows client libraries for IRP systems to normalize an expression from whatever language projection is appropriate (e.g. LINQ in C# and VB, fluent interface patterns in Java, JavaScript, Python, etc.) to a normal form. As an example, consider the following streaming equivalent query:

code:C#

var ctx = new ClientContext(); // IRP

var res = from p in ctx.GetObservable<Product>("Products")

where p.UnitPrice > 49.95m

select p.ProductName;

await res.SubscribeAsync(...);

IAsyncReactiveQbservable<T>空間（LINQ to SQLのIQueryable<T>ではなく）で定式化されたクエリ式に純粋に注目すると、次のような式表現になります。

Focusing purely on the query expression formulated in the IAsyncReactiveQbservable<T> space (rather than IQueryable<T> in LINQ to SQL), we end up with an expression representation that looks like this:

code:query

Call(

methodinfoof(AsyncReactiveQbservable.Select<Product, string>),

Call(

methodinfoof(AsyncReactiveQbservable.Where<Product, Product>),

Parameter(

typeof(IAsyncReactiveQueryable<Product>),

"Products"

),

Lambda(

Member(p, propertyinfoof(Product.ProductName)),

p

)

),

Lambda(

GreaterThan(

Member(p, propertyinfoof(Product.UnitPrice)),

Constant(49.95)

),

p

)

)

この表現をクライアント言語診断フォーマットに正規化するためには、クライアント固有のリフレクション、特にクエリ演算子を表すMethodInfoオブジェクトへの参照をすべて取り除く必要があります。これは、これらのメソッドに識別子を関連付けることで達成されます。

In order to normalize this expression into a client language-agnostics format, we need to shake off all references to reflection that’s client-specific, in particular the MethodInfo objects representing query operators. This is achieved by associating an identifiers with these methods:

code:C#

static class AsyncReactiveQbservable

{

public static IAsyncReactiveQbservable<T> Where<T>(this IAsyncReactiveQbservable<T> source, Expression<Func<T, bool>> predicate) { ... }

public static IAsyncReactiveQbservable<R> Select<T, R>(this IAsyncReactiveQbservable<T> source, Expression<Func<T, R>> selector) { ... }

}

ノーマライザは、これらの KnownResource 属性を拾い、MethodCallExpression ノードを InvocationExpresson ノードに変換します。例えば、以下のようになります。

The normalizer will pick up on these KnownResource attributes and turn MethodCallExpression nodes into InvocationExpresson nodes where the MethodInfo gets subsituted for an unbound ParameterExpression using the identifier specified. For example:

code:query

Invoke(

Parameter(

typeof(Func<IAsyncReactiveQbservable<Product>, Expression<Func<Product, string>>, IAsyncReactiveQbservable<string>>),

"rx://operators/map"

),

Invoke(

Parameter(

typeof(Func<IAsyncReactiveQbservable<Product>, Expression<Func<Product, Product>>, IAsyncReactiveQbservable<Product>>),

"rx://operators/filter"

),

Parameter(

typeof(IAsyncReactiveQueryable<Product>),

"Products"

),

Lambda(

Member(p, propertyinfoof(Product.ProductName)),

p

)

),

Lambda(

GreaterThan(

Member(p, propertyinfoof(Product.UnitPrice)),

Constant(49.95)

),

p

)

)

データモデルに準拠したProduct型のプロパティにMapping属性を使用することで、上に示したメソッドのKnownResourceと同様の方法で、PropertyInfoオブジェクトへの依存性をさらに取り除くことができます。その結果、クライアントのみのリフレクション・オブジェクトに依存しない表現となります。

The use of Mapping attributes on the properties of the Data Model compliant Product type are further used to remove the dependency on PropertyInfo objects, in a way similar to KnownResource for the methods shown above. The result is an expression that’s independent of client-only reflection objects.

KnownResourceの使用は、クライアントができるだけ自然にクエリの意図を表現できるようにするための、クライアント側の便宜的なメカニズムに過ぎないことに注意してください。C#、Visual Basic、F#、.NET以外の言語やフレームワークで書かれたIRPクライアントは、そのような環境で利用可能なメカニズムを活用して同様の効果を得ることができます。メタデータの属性を利用して正規化を行う機能は、IRPのコア機能の上に乗っかっている構文上の飾りであるため、GetObservableメソッドを明示的に呼び出して、クエリ演算子のプロキシを取得することで、上記と同じクエリを書くことができます。

Note that the use of KnownResource is merely a client-side convenience mechanism in order to make expressing query intent as natural as possible for clients. IRP clients written in languages and frameworks other than C#, Visual Basic, F#, and .NET can leverage the mechanisms available in such environments to achieve similar effects. Given that this facility of using metadata attributes to drive normalization is a syntactic sugar veneer on top of the core IRP facilities, it’s possible to write the same query as above using explicit calls to GetObservable methods to obtain proxies to the query operators:

code:C#

var ctx = new ClientContext(); // IRP

var products = ctx.GetObservable<Product>("Products");

var where = ctx.GetObservable<IAsyncReactiveQbserver<Product>, Expression<Func<Product, bool>>, Product>(new Uri("rx://operators/filter");

var select = ctx.GetObservable<IAsyncReactiveQbserver<Product>, Expression<Func<Product, string>>, string>(new Uri("rx://operators/map");

var res = select(where(products, p => p.UnitPrice > 49.95m), p => p.ProductName);

await res.SubscribeAsync(...);

これは、全く同じ正規化された式のツリーを生成し、うまく設計された言語投影（C#の拡張メソッドとクエリ式の構文を用いた流暢なインターフェースパターンなど）が、ユーザーの意図を形成する際の複雑さの多くを隠すことができることを示す例として機能します。

This will produce exactly the same normalized expression tree and acts as an example to show how a well-designed language projection (such as fluent interface patterns with extension methods and query expression syntax in C#) can hide a lot of the complexity in formulating user intent.

リフレクション・オブジェクトへの参照を消去して、結合されていないグローバル・パラメータを参照する呼び出し式に変更する（ソース、シンク、演算子などのアーティファクトを識別する）以外にも、正規化にはさまざまなステップがあります。

Besides the erasure of references to reflection objects in favor of invocation expressions referring to unbound global parameters (identifying artifacts such as sources, sinks, and operators), the normalization also includes a variety of other steps:

副作用のない、部分式のローカルな部分評価

Local partial evaluation of subexpressions that are free of side-effects.

様々な形式の（オプションの）表現の最適化

Various forms of (optional) expression optimization.

n-ary関数の呼び出しを単項関数のタプルベースの呼び出しに書き換えることによる関数呼び出しの正規化。

Normalization of function invocations by rewriting n-ary function invocations to tuple-based invocation of unary functions.

安定した正規形を維持しつつ、言語投影の親しみやすさを向上させるために、IRP（より一般的には任意の計算式のためのICP）の将来の反復は、おそらくさらなるマッピングの自由を含むでしょう。例えば、様々な演算子がcurried関数として扱われることで、部分的に応用して特殊なマクロを定義したり、他の言語でより自然な投影を行ったりすることが可能になります（例えば、関数がcurriedであるF#やScalaなど）。演算子の呼び出しを「タプル正規形」で正規化するだけではなく、「カリー正規形」を追加しています。

Future iterations of IRP (and more generally ICP for arbitrary computation expressions) will likely contain further mapping freedom in order to increase the friendliness of the language projection while retaining a stable normal form. For example, various operators can benefit from being treated as curried functions, thus enabling partial application to define specialized macros, or a more natural projection in other languages (e.g. F# or Scala where functions are curried). Rather than only normalizing operator invocations using a “tuple normal form”, this introduces the addition of a “curry normal form”.